package sort;

/**
 * Created with IntelliJ IDEA.
 * Description: 快速排序
 * User: Li_yizYa
 * Date: 2025/9/8
 * Time: 22:39
 */
// 6  5  4  4  3  1  2  10  8
// p
public class QuickSort {
    private static void quickSort(int[] nums, int start, int end) {
        if (start >= end) {
            return;
        }
        int pivot = partition(nums, start, end);
        quickSort(nums, start, pivot - 1);
        quickSort(nums, pivot + 1, end);
    }
    private static int partition(int[] nums, int left, int right) {
        int tmp = nums[left];
        while (left < right) {
            // 找到右边第一个比tmp小的
            while (left < right && nums[right] >= tmp) {
                right--;
            }
            nums[left] = nums[right];
            // 找到左边第一个比tmp大的
            while (left < right && nums[left] <= tmp) {
                left++;
            }
            nums[right] = nums[left];
        }
        nums[left] = tmp;
        return left;
    }

    public static void main(String[] args) {
        int[] nums = {6,5,4,4,3,1,2,10,8};
        quickSort(nums, 0, nums.length - 1);
        for (int num : nums) {
            System.out.print(num + " ");
        }
    }
//    public static void quickSort(int[] nums, int start, int end) {
//        if (start >= end) {
//            return;
//        }
//        int pivot = partition(nums, start, end);
//        quickSort(nums, start, pivot - 1);
//        quickSort(nums, pivot + 1, end);
//    }
//
//    private static int partition(int[] nums, int left, int right) {
//        int tmp = nums[left];
//        while (left < right) {
//            // 从右边找到第一个比它小的值
//            while (left < right && nums[right] >= tmp) {
//                right--;
//            }
//            nums[left] = nums[right];
//
//            // 从左边找第一个大于它的值
//            while (left < right && nums[left] <= tmp) {
//                left++;
//            }
//            nums[right] = nums[left];
//        }
//        nums[left] = tmp;
//        return left;
//    }
}
